#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<windows.h>

//5.3 搜索节点的表示与存储结构设计
typedef struct
{
    double x1,x2,y;
}DOT;

//5.4 多元函数极值求解
//5.4.1 多元函数值计算
double fun(double x1,double x2)
{
    double y;
    y=3*(1-x1)*(1-x1)*exp(-(x1)*(x1)-(x2+1)*(x2+1))-10*(x1/5-x1*x1*x1-x2*x2*x2*x2*x2)*exp(-x1*x1-x2*x2)-exp(-(x1+1)*(x1+1)-x2*x2)/3;
    return y;
}

//5.4.2 派生最近邻的8个节点

#define LEFT -5
#define RIGHT 5
#define NEIGHBORNUM 8

DOT *Expand(DOT point,double delta,double (*fun)())
{
    int i=0;
    double x1,x2;
    DOT *neighbors;
    neighbors=(DOT *)malloc(sizeof(DOT)*NEIGHBORNUM);
    for(x1=point.x1-delta;x1<=point.x1+delta;x1+=delta)
    {
        for(x2=point.x2-delta;x2<=point.x2+delta;x2+=delta)
        {
            if(fabs(point.x1-x1)<1e-10&&fabs(point.x2-x2)<1e-10)    continue;
            neighbors[i].x1=x1<LEFT?LEFT:(x1>RIGHT?RIGHT:x1);
            neighbors[i].x2=x2<LEFT?LEFT:(x2>RIGHT?RIGHT:x2);
            neighbors[i].y=fun(x1,x2);
            i++;
        }
    }
    return neighbors;
}

//5.4.3 回收节点的数据存储单元
void ClearAllNeighbors(DOT *neighbors)
{
    free(neighbors);
}

//5.4.4 随机初始化搜索节点
void InitPoint(DOT *point)
{
    srand((unsigned)time(NULL));
    point->x1=rand()%(int)(RIGHT-LEFT)+LEFT;
    point->x2=rand()%(int)(RIGHT-LEFT)+LEFT;
    point->y=fun(point->x1,point->x2);
}

//5.4.5 局部最优搜索实现
#define TRUE 1
#define FALSE 0
typedef int STATUS;

void SearchResult_by_Mini(double delta,double (*fun)(),DOT *result)
{
    STATUS flag=FALSE;
    DOT point,*neighbors;
    int i;
    InitPoint(&point);
    printf("Init Fun(%lf,%lf)=%lf\n",point.x1,point.x2,point.y);
    while(TRUE)
    {
        neighbors=Expand(point,delta,fun);
        for(i=0;i<NEIGHBORNUM;i++)
        {
            if(point.y<neighbors[i].y)
            {
                flag=TRUE;
                point=neighbors[i];
                break;
            }
        }
        if(flag==TRUE)
        {
            flag=FALSE;
        }
        else
        {
            break;
        }
        ClearAllNeighbors(neighbors);
    }
    *result=point;
}

//5.4.M 主程序
void main()
{
    DOT result;
    double delta=0.0001;
    int i,j,k;
    for(i=0;i<10;i++)
    {
        SearchResult_by_Mini(delta,fun,&result);
        printf("Resu Fun(%lf,%lf)=%lf\n",result.x1,result.x2,result.y);
        printf("=================\n");
        Sleep(3000);
    }
}